МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
Лабораторна робота №3
СТВОРЕННЯ I ВЕДЕННЯ БІНАРНИХ ДЕРЕВ
з курсу: “Алгоритми и структури данних”
Виконав студент
групи КН – 24
Прийняв
ЛЬВІВ 2007
Мета роботи
Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi бінарних дерев. Оволодiти методами роботи iз бінарними деревами.
Теоретичні відомості
Для описання будь-якої структури, яка характеризується ієрархiчними зв'язками, є корисними дерева.
Існує два типи схем, що використовуються у дослідженнях генеалогії. Перший тип називається схемою родоводу, другий - схемою нащадків.
Якими б не були дерева, усі вони мають набір спільних властивостей. У кожному дереві є визначений вузол - корінь. Вузол, у якого немає нащадків, називається термінальним вузлом, або листом. Всі інші вузли називаються гілковими вузлами.
Дерево - це визначена множина одного чи кількох вузлів, таких, що:
Є спеціально визначений вузол, що називається коренем.
Інші вузли є розділениними на підмножини, що не перетинаються Т1, Т2, Т3,..., Тn (n>=0), кожна з яких є деревом. Кожне Ті(1<=i<=n) називається піддеревом вузла.
Рівнем вузла є 1 плюс довжина шляху до нього від кореня.
Степенем вузла є кількість піддерев, які з нього виходять.
Впорядкованим називається дерево, у якого вузли на кожному рівні впорядковані певним чином.
Якщо видалити корінь із гілками, то отримується множина незв'язаних дерев. Кожен набір незв'язаних дерев називається лісом.
Якщо степінь кожного вузла є меншим або дорiвнює 2, то дерево називається бінарним.
Бінарним деревом називається множина m (m>=0) вузлів, що є або порожньою (m=0), або містить кореневий вузол, який має два незв'язаних бінарних піддерева, що називається лівим піддеревом і правим піддеревом.
Бінарне дерево, у якого кожний вузол має степінь 0 чи 2, називається повністю бінарним деревом.
Оскільки бінарні дерева легко зображати і маніпулювати з ними, зручно перетворити будь-яке дерево в еквівалентну бінарну форму (якщо можливо).
Індивідуальне завдання
Реалізувати бінарне дерево.
Текст програми:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
//-----DATA SRUCTURES----------
typedef char type_of_element;
struct unit
{
type_of_element key;
unit * left;
unit * right;
unit * parent;
};
//----------------------------
void tree_insert(unit **, type_of_element);
void inorder_tree_walk(unit *);
unit * tree_search(unit *, type_of_element);
unit * initialization_tree(void);
unit * tree_minimum (unit *);
unit * tree_successor(unit *);
unit * tree_delete(unit *, unit *);
//--------MAIN---------------
void main (void)
{
unit * root;
root=initialization_tree();
type_of_element element;
while (1)
{
printf ("\n 1 - add element\n2 - delete element\n 3 - show tree \n4 - exit \n");
int answer;
scanf(" %d",&answer);
switch (answer)
{
case 1:{ printf("\n Enter the key of current element\n");
scanf(" %c",&element);
tree_insert(&root,element);
}; break;
case 2:{ type_of_element symbol;
printf("\n Enter the key of element \n");
scanf(" %c",&symbol);
tree_delete(root, tree_search(root, symbol));
}; break;
case 3:{ inorder_tree_walk(root); }; break;
default:{ printf("\n Good bye \n"); goto l1; }
}
}
l1: getch();
}
//----INSERTING FUNCTION-------------
void tree_insert(unit ** root, type_of_element element)
{
unit * run_pointer,* pointer, * inserting_unit;
pointer=(*root);
run_pointer=NULL;
//-----NEW UNIT------
inserting_unit=(unit *)malloc(sizeof(struct unit));
inserting_unit->left=NULL;
inserting_unit->right=NULL;
inserting_unit->parent=NULL;
inserting_unit->key=element;
//-------------------
while (pointer!=NULL)
{
run_pointer=pointer;
if (element<pointer->key) pointer=pointer->left;
else pointer=pointer->right;
}
inserting_unit->parent=run_pointer;
if (run_po...
